package com.ztom.daily.n2022.m3;

/**
 * 统计按位或能得到最大值的子集数目
 * <p>
 * https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets/
 *
 * @author ZhangTao
 */
public class Day15CountMaxOrSubsets {

    public int countMaxOrSubsets1(int[] nums) {
        int maxOr = 0, cnt = 0;
        // 总共有 2 ^ n - 1 个子集
        for (int i = 0; i < 1 << nums.length; i++) {
            int orVal = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((i >> j) & 1) == 1) {
                    orVal |= nums[j];
                }
            }
            if (orVal > maxOr) {
                maxOr = orVal;
                cnt = 1;
            } else if (orVal == maxOr) {
                cnt++;
            }
        }
        return cnt;
    }

    public int countMaxOrSubsets(int[] nums) {
        int max = 0;
        for (int num : nums) {
            max |= num;
        }

        return dfs(nums, 0, 0, max);
    }

    private int dfs(int[] nums, int i, int cur, int max) {
        if (i == nums.length) {
            return cur == max ? 1 : 0;
        }
        // 选择当前 + 不选当前
        return dfs(nums, i + 1, cur | nums[i], max)
                + dfs(nums, i + 1, cur, max);
    }
}
